// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-27 17:15
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

public class CanCompleteCircuit {
    // 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            if (ifTravel(gas, cost, i)) {
                return i;
            }
        }
        return -1;
    }

    private boolean ifTravel(int[] gas, int[] cost, int i) {
        // 判断当前下标的节点是否可以乘车返回原点
        int g = gas[i];
        int len = gas.length;
        for (int j = 1; j <= len; j++) {
            i = (i + 1) % len;
            g -= cost[((i - 1) + len) % len];
            if (g < 0) {
                return false; // 无法驶达目的地
            } else {
                g += gas[i]; // 到达目的地i，并且获取i的油
            }
        }
        return true;
    }
}
